The present invention relates to Reed-Solomon (RS) decoders. More particularly, the present invention relates a runtime programable RS decoder that can operate on multiple pieces of data during one clock cycle in order to generate, reduce, and evaluate polynomials involved in the decoding of an RS code, and which allows a user to choose the RS code after the circuit has been implemented.
RS codes are used in many applications where data is transferred from one system to another. These applications include Digital Subscriber Lines (xDSL), digital television, asynchronous transfer mode (ATM) communications, tape drives, compact discs (CDs), digital versatile discs (DVDs), and so on. The decoding of RS error correcting codes requires the calculation of several polynomials with coefficients in a finite Galois Field (GF). These polynomials are generally known as the syndrome polynomial, the error evaluator polynomial (xcexa9(x) polynomial) and the error locator polynomial (xcex9(x) polynomial). Conventional designs for computing these polynomials required circuitry that was generally limited to operating on one byte at a time for the computation of each of these polynomials, such as shown in U.S. Pat. No. 5,396,502 (hereinafter the ""502 patent). The ""502 patent describes an Error Correction Unit (ECU) that uses a single stack embodiment for the generation, reduction and evaluation of the polynomials involved in the decoding of an RS code. The circuit uses the same hardware to generate the syndromes, reduce the xcexa9(x) and xcex9(x) polynomials and evaluate the xcexa9(x) and xcex9(x) polynomials, but is limited to operating on one byte per clock cycle. The disclosure of the ""502 patent is hereby incorporated herein in its entirety.
Additionally, RS decoders in the past were typically limited to being able to decode only a particular RS code. It was not possible with such RS decoders to choose the code after the circuit was implemented so as to enable use in multiple applications without predetermining the RS code. Such decoders did not allow a user the flexibility to change the RS code as desired without having to replace the RS decoder.
In view of the aforementioned shortcomings associated with conventional RS decoders, there is a strong need in the art for an RS decoder which is not limited to operating on one byte per clock cycle. Moreover, there is a strong need in the art for an RS decoder which is not limited in operation based on a set predefined RS code.
The RS decoder of the present invention provides improved operation compared to conventional RS decoders. According to the present invention, an RS decoder is provided which is able to operate on two or more words per clock cycle. Such a feature will reduce the decoding time to a point approaching the time it takes to generate the xcex9 and xcexa9 polynomials. In addition, the RS decoder is runtime programmable, which allows a user to change the codefield after the circuit has been implemented (i.e. xe2x80x9con the fly.xe2x80x9d)
More particularly, the present invention is a decoder circuit for decoding an input word stream which includes a plurality of Reed-Solomon encoded data segments. The decoder circuit includes at least one computation unit for receiving the input bit stream, resolving coefficients of a syndrome polynomial, generating an xcexa9(x) polynomial, generating a xcex9(x) polynomial, and generating a xcex9xe2x80x2(x) polynomial, and for outputting an evaluated xcexa9(x) polynomial and an evaluated xcex9(x) polynomial, each of these polynomials having a plurality of data words which the computation unit can resolve multiple words at a time. The decoder circuit has at least one register file for receiving data and storing the intermediate processed coefficients of the syndrome polynomial, the xcexa9(x) polynomial, the xcex9(x) polynomial, and the xcex9xe2x80x2(x) polynomial. Additionally, the decoder circuit has at least one division unit for evaluating the xcexa9(x) and xcex9(x) polynomials and for producing an output word stream of decoded data segments.
Additionally, the computation unit of FIG. 1 has a general GF multiplier, which uses a primitive element of the field as an input. This allows the user to change the field xe2x80x9con the fly.xe2x80x9d Traditional GF multipliers are polynomial specific, and if implemented in an ASIC or ASSP can only handle one field. The current invention allows the user to decode data encoded in any RS code of bit width less than a defined maximum, as long as the defining parameters of the code are known. Likewise, the GF multiplier can handle codes of lesser bit widths than the maximum defined by the size of the multipliers.